The development and application of rule engines is one branch of Artificial Intelligence (A.I.), which is a very broad research area that focuses on “making computers think like people.” Broadly speaking, a rule engine processes information by applying rules to data objects (also known as facts). A rule is a logical construct for describing the operations, definitions, conditions, and/or constraints that apply to some predetermined data to achieve a goal. Various types of rule engines have been developed to evaluate and process rules. One conventional type of rule engines is Rete rule engines. A Rete rule engine implements a Rete network to process rules and data objects, such as the example shown in FIG. 1. A Rete network includes many different types of nodes, including, for example, ObjectType Nodes, Alpha Nodes, LeftInputAdapter Nodes, Eval Nodes, Rete Nodes, Join Nodes, Not Nodes, and Terminal Nodes. Referring to FIG. 1, the Rete network 100 includes two ObjectType Nodes 111 and 121, two Alpha Nodes 113 and 123, a LeftInputAdapter Node 115, a Join Node 130, and a Terminal Node 140.
Data objects enter a Rete network at the root node, from which they are propagated to any matching ObjectType Nodes. From a ObjectType Node, a data object is propagated to either an Alpha Node (if there is a literal constraint), a LeftInputAdapter Node (if the data object is the left most object type for the rule), or a Beta Node. For example, referring to FIG. 1, a data object 101 is propagated to a matching ObjectType Node 111. From the ObjectType Node 111, the data object 101 is propagated to an Alpha Node 113, and then to a LeftInputAdapter Node 115. Connected to the LeftInputAdapter Node 115 is a Join Node 130, which is an example of a Beta Node.
A Beta Node has two inputs, unlike one-input nodes, such as ObjectType Nodes and AlphaNodes. A Beta Node can receive Tuples in its left-input and Objects in its right-input. Join Node, Not Node, and Exists Node are some examples of Beta Nodes. All nodes may have memory to store a reference to the Objects and Tuples propagated to them, if any. The LeftInputAdapter Node creates a Tuple with a single Object and propagates the Tuple created to the left-input of the first Beta Node connected to the LeftInputAdapter Node, where the Tuple is placed in the left-input memory of the Beta Node and then join attempts are made with all the Objects on the right-input side. For example, the LeftInputAdapter Node 115 creates a Tuple from the data object 101 and propagates the Tuple to the Join Node 130.
When an Object enters the right-input of a Beta Node, the Object is placed in the right-input memory and join attempts are made with all the Tuples in the left-input memory. If a join attempt is successful, the Object is added to the Tuple and then propagated to the left-input of the next node until the Tuple reaches a Terminal Node. The Tuples stored in the left-inputs are partially matched. When the Tuple reaches the Terminal Node, the Tuple is fully matched. For example, if the Tuple 103 in FIG. 1 successfully joins with an object from the right input of the Join Node 130, then the Tuple 103 is propagated to the Terminal Node 140. At a Terminal Node, an activation is created from the fully matched Tuple and the corresponding Rule. The activation is placed onto an Agenda of the Rete rule engine for potential firing or potential execution.
Since there may be multiple activations in the Agenda, the Agenda typically include a conflict resolution mechanism (e.g., a priority queue) to determine the order in which the activations have to be fired. Conventionally, the Rete rule engine uses a lot of memory in order to store the Objects and the Tuples as the Objects and the Tuples propagate through the Rete network. However, for stateless applications, in which the rules and the data objects remain unchanged after the initial assertion, much of the memory used by the Rete rule engine may be unnecessary and the complex conflict resolution mechanism further lowers the efficiency of the Rete rule engine.
Furthermore, exploiting multiple threads for conventional Rete rule engine is hard, as it is hard to predict when and if a Tuple is going to enter the left-input or an Object is going to enter the right-input of a node. Reads and writes can happen simultaneously. One existing technique to solve the above problem is to add locks to control when reads and writes may occur. But adding locks is expensive and past research has shown the cost of adding locks is more than the cost of using lock free single thread approach.